home *** CD-ROM | disk | FTP | other *** search
/ SGI Freeware 2002 November / SGI Freeware 2002 November - Disc 2.iso / dist / fw_glimpse.idb / usr / freeware / src / glimpse-3.0 / agrep / asplit.c.z / asplit.c
C/C++ Source or Header  |  1997-09-09  |  11KB  |  392 lines
  1. /* Copyright (c) 1994 Burra Gopal, Udi Manber.  All Rights Reserved. */
  2.  
  3. #include "agrep.h"
  4.  
  5. #include "putils.c"
  6.  
  7. extern int checksg();
  8. extern int D;
  9. extern FILE *debug;
  10.  
  11. /* All borrowed from agrep.c and are needed for searching the index */
  12. extern    ParseTree aterminals[MAXNUM_PAT];
  13. extern int    AComplexBoolean;
  14.  
  15. /* returns where it found the distinguishing token: until that from prev value of begin is the current pattern (not just the "words" in it) */
  16. CHAR *
  17. aparse_flat(begin, end, prev, next)
  18.     CHAR    *begin;
  19.     CHAR    *end;
  20.     int    prev;
  21.     int    *next;
  22. {
  23.     if (begin > end) {
  24.         *next = prev;
  25.         return end;
  26.     }
  27.  
  28.     if (prev & ENDSUB_EXP) prev &= ~ATTR_EXP;
  29.     if ((prev & ATTR_EXP) && !(prev & VAL_EXP)) prev |= VAL_EXP;
  30.  
  31.     while (begin <= end) {
  32.         if (*begin == ',') {
  33.             prev |= OR_EXP;
  34.             prev |= VAL_EXP;
  35.             prev |= ENDSUB_EXP;
  36.             if (prev & AND_EXP) {
  37.                 fprintf(stderr, "parse error at character '%c'\n", *begin);
  38.                 return NULL;
  39.             }
  40.             *next = prev;
  41.             return begin;
  42.         }
  43.         else if (*begin == ';') {
  44.             prev |= AND_EXP;
  45.             prev |= VAL_EXP;
  46.             prev |= ENDSUB_EXP;
  47.             if (prev & OR_EXP) {
  48.                 fprintf(stderr, "parse error at character '%c'\n", *begin);
  49.                 return NULL;
  50.             }
  51.             *next = prev;
  52.             return begin;
  53.         }
  54.         else if (*begin == '\\') begin ++;    /* skip two things */
  55.         begin++;
  56.     }
  57.  
  58.     *next = prev;
  59.     return begin;
  60. }
  61.  
  62. int
  63. asplit_pattern_flat(APattern, AM, terminals, pnum_terminals, pAParse)
  64.     CHAR    *APattern;
  65.     int    AM;
  66.     ParseTree terminals[MAXNUM_PAT];
  67.     int    *pnum_terminals;
  68.     int    *pAParse;
  69. {
  70.     CHAR  *buffer;
  71.     CHAR  *buffer_pat;
  72.     CHAR  *buffer_end;
  73.  
  74.     buffer = APattern;
  75.     buffer_end = buffer + AM;
  76.     *pAParse = 0;
  77.  
  78.     /*
  79.      * buffer is the runnning pointer, buffer_pat is the place where
  80.      * the distinguishing delimiter was found, buffer_end is the end.
  81.      */
  82.      while (buffer_pat = aparse_flat(buffer, buffer_end, *pAParse, pAParse)) {
  83.         /* there is no pattern until after the distinguishing delimiter position: some agrep garbage */
  84.         if (buffer_pat <= buffer) {
  85.             buffer = buffer_pat+1;
  86.             if (buffer_pat >= buffer_end) break;
  87.             continue;
  88.         }
  89.         if (*pnum_terminals >= MAXNUM_PAT) {
  90.             fprintf(stderr, "boolean expression has too many terms\n");
  91.             return -1;
  92.         }
  93.         terminals[*pnum_terminals].op = 0;
  94.         terminals[*pnum_terminals].type = LEAF;
  95.         terminals[*pnum_terminals].terminalindex = *pnum_terminals;
  96.         terminals[*pnum_terminals].data.leaf.attribute = 0;    /* default is no structure */
  97.         terminals[*pnum_terminals].data.leaf.value = (CHAR *)malloc(buffer_pat - buffer + 2);
  98.         memcpy(terminals[*pnum_terminals].data.leaf.value, buffer, buffer_pat - buffer);    /* without distinguishing delimiter */
  99.         terminals[*pnum_terminals].data.leaf.value[buffer_pat - buffer] = '\0';
  100.         (*pnum_terminals)++;
  101.         if (buffer_pat >= buffer_end) break;
  102.         buffer = buffer_pat+1;
  103.     }
  104.     if (buffer_pat == NULL) return -1;    /* got out of while loop because of NULL rather than break */
  105.     return(*pnum_terminals);
  106. }
  107.  
  108. /*
  109.  * Recursive descent; C-style => AND + OR have equal priority => must bracketize expressions appropriately or will go left->right.
  110.  * Grammar:
  111.  *     E = {E} | ~a | ~{E} | E ; E | E , E | a
  112.  * Parser:
  113.  *    One look ahead at each literal will tell you what to do.
  114.  *    ~ has highest priority, ; and , have equal priority (left to right associativity), ~~ is not allowed.
  115.  */
  116. ParseTree *
  117. aparse_tree(buffer, len, bufptr, terminals, pnum_terminals)
  118.     CHAR    *buffer;
  119.     int    len;
  120.     int    *bufptr;
  121.     ParseTree terminals[];
  122.     int    *pnum_terminals;
  123. {
  124.     int    token, tokenlen;
  125.     CHAR    tokenbuf[MAXNAME];
  126.     int    oldtokenlen;
  127.     CHAR    oldtokenbuf[MAXNAME];
  128.     ParseTree *t, *n, *leftn;
  129.  
  130.     token = get_token_bool(buffer, len, bufptr, tokenbuf, &tokenlen);
  131.     switch(token)
  132.     {
  133.     case    '{':    /* (exp) */
  134.         if ((t = aparse_tree(buffer, len, bufptr, terminals, pnum_terminals)) == NULL) return NULL;
  135.         if ((token = get_token_bool(buffer, len, bufptr, tokenbuf, &tokenlen)) != '}') {
  136.             fprintf(stderr, "parse error at offset %d\n", *bufptr);
  137.             destroy_tree(t);
  138.             return (NULL);
  139.         }
  140.         if ((token = get_token_bool(buffer, len, bufptr, tokenbuf, &tokenlen)) == 'e') return t;
  141.         switch(token)
  142.         {
  143.         /* must find boolean infix operator */
  144.         case ',':
  145.         case ';':
  146.             leftn = t;
  147.             if ((t = aparse_tree(buffer, len, bufptr, terminals, pnum_terminals)) == NULL) return NULL;
  148.             n = (ParseTree *)malloc(sizeof(ParseTree));
  149.             n->op = (token == ';') ? ANDPAT : ORPAT ;
  150.             n->type = INTERNAL;
  151.             n->data.internal.left = leftn;
  152.             n->data.internal.right = t;
  153.             return n;
  154.  
  155.         /* or end of parent sub expression */
  156.         case '}':
  157.             unget_token_bool(bufptr, tokenlen);    /* part of someone else who called me */
  158.             return t;
  159.  
  160.         default:
  161.             destroy_tree(t);
  162.             fprintf(stderr, "parse error at offset %d\n", *bufptr);
  163.             return NULL;
  164.         }
  165.  
  166.     /* Go one level deeper */
  167.     case    '~':    /* not exp */
  168.         if ((token = get_token_bool(buffer, len, bufptr, tokenbuf, &tokenlen)) == 'e') return NULL;
  169.         switch(token)
  170.         {
  171.         case 'a':
  172.             if (*pnum_terminals >= MAXNUM_PAT) {
  173.                 fprintf(stderr, "Pattern expression too large (> %d)\n", MAXNUM_PAT);
  174.                 return NULL;
  175.             }
  176.             n = &terminals[*pnum_terminals];
  177.             n->op = 0;
  178.             n->type = LEAF;
  179.             n->terminalindex = (*pnum_terminals);
  180.             n->data.leaf.attribute = 0;
  181.             n->data.leaf.value = (unsigned char*)malloc(tokenlen + 2);
  182.             memcpy(n->data.leaf.value, tokenbuf, tokenlen);
  183.             n->data.leaf.value[tokenlen] = '\0';
  184.             (*pnum_terminals)++;
  185.             n->op |= NOTPAT;
  186.             t = n;
  187.             break;
  188.  
  189.         case '{':
  190.             if ((t = aparse_tree(buffer, len, bufptr, terminals, pnum_terminals)) == NULL) return NULL;
  191.             if (t->op & NOTPAT) t->op &= ~NOTPAT;
  192.             else t->op |= NOTPAT;
  193.             if ((token = get_token_bool(buffer, len, bufptr, tokenbuf, &tokenlen)) != '}') {
  194.                 fprintf(stderr, "parse error at offset %d\n", *bufptr);
  195.                 destroy_tree(t);
  196.                 return NULL;
  197.             }
  198.             break;
  199.  
  200.         default:
  201.             fprintf(stderr, "parse error at offset %d\n", *bufptr);
  202.             return NULL;
  203.         }
  204.         /* The resulting tree is in t. Now do another lookahead at this level */
  205.  
  206.         if ((token = get_token_bool(buffer, len, bufptr, tokenbuf, &tokenlen)) == 'e') return t;
  207.         switch(token)
  208.         {
  209.         /* must find boolean infix operator */
  210.         case ',':
  211.         case ';':
  212.             leftn = t;
  213.             if ((t = aparse_tree(buffer, len, bufptr, terminals, pnum_terminals)) == NULL) return NULL;
  214.             n = (ParseTree *)malloc(sizeof(ParseTree));
  215.             n->op = (token == ';') ? ANDPAT : ORPAT ;
  216.             n->type = INTERNAL;
  217.             n->data.internal.left = leftn;
  218.             n->data.internal.right = t;
  219.             return n;
  220.  
  221.         case '}':
  222.             unget_token_bool(bufptr, tokenlen);
  223.             return t;
  224.  
  225.         default:
  226.             destroy_tree(t);
  227.             fprintf(stderr, "parse error at offset %d\n", *bufptr);
  228.             return NULL;
  229.         }
  230.  
  231.     case    'a':    /* individual term (attr=val) */
  232.         if (tokenlen == 0) return NULL;
  233.         memcpy(oldtokenbuf, tokenbuf, tokenlen);
  234.         oldtokenlen = tokenlen;
  235.         oldtokenbuf[oldtokenlen + 1] = '\0';
  236.         token = get_token_bool(buffer, len, bufptr, tokenbuf, &tokenlen);
  237.         switch(token)
  238.         {
  239.         case '}':    /* part of case '{' above: else syntax error not detected but semantics ok */
  240.             unget_token_bool(bufptr, tokenlen);
  241.         case 'e':    /* endof input */
  242.         case ',':
  243.         case ';':
  244.             if (*pnum_terminals >= MAXNUM_PAT) {
  245.                 fprintf(stderr, "Pattern expression too large (> %d)\n", MAXNUM_PAT);
  246.                 return NULL;
  247.             }
  248.             n = &terminals[*pnum_terminals];
  249.             n->op = 0;
  250.             n->type = LEAF;
  251.             n->terminalindex = (*pnum_terminals);
  252.             n->data.leaf.attribute = 0;
  253.             n->data.leaf.value = (unsigned char*)malloc(oldtokenlen + 2);
  254.             strcpy(n->data.leaf.value, oldtokenbuf);
  255.             (*pnum_terminals)++;
  256.             if ((token == 'e') || (token == '}')) return n;    /* nothing after terminal in expression */
  257.  
  258.             leftn = n;
  259.             if ((t = aparse_tree(buffer, len, bufptr, terminals, pnum_terminals)) == NULL) return NULL;
  260.             n = (ParseTree *)malloc(sizeof(ParseTree));
  261.             n->op = (token == ';') ? ANDPAT : ORPAT ;
  262.             n->type = INTERNAL;
  263.             n->data.internal.left = leftn;
  264.             n->data.internal.right = t;
  265.             return n;
  266.  
  267.         default:
  268.             fprintf(stderr, "parse error at offset %d\n", *bufptr);
  269.             return NULL;
  270.         }
  271.  
  272.     case    'e':    /* can't happen as I always do a lookahead above and return current tree if e */
  273.     default:
  274.         fprintf(stderr, "parse error at offset %d\n", *bufptr);
  275.         return NULL;
  276.     }
  277. }
  278.  
  279. int
  280. asplit_pattern(APattern, AM, terminals, pnum_terminals, pAParse)
  281.     CHAR    *APattern;
  282.     int    AM;
  283.     ParseTree terminals[];
  284.     int    *pnum_terminals;
  285.     ParseTree **pAParse;
  286. {
  287.     int    bufptr = 0, ret, i, j;
  288.  
  289.     if (is_complex_boolean(APattern, AM)) {
  290.         AComplexBoolean = 1;
  291.         *pnum_terminals = 0;
  292.         if ((*pAParse = aparse_tree(APattern, AM, &bufptr, terminals, pnum_terminals)) == NULL)
  293.             return -1;
  294.         /* print_tree(*pAParse, 0); */
  295.         return *pnum_terminals;
  296.     }
  297.     else {
  298.         for (i=0; i<AM; i++) {
  299.             if (APattern[i] == '\\') i++;
  300.             else if ((APattern[i] == '{') || (APattern[i] == '}')) {
  301.                 /* eliminate it from pattern by shifting (including '\0') since agrep must essentially do a flat search */
  302.                 for (j=i; j<AM; j++)
  303.                     APattern[j] = APattern[j+1];
  304.                 AM --;
  305.                 i--;    /* to counter the ++ on top */
  306.             }
  307.         }
  308.  
  309.         AComplexBoolean = 0;
  310.         *pnum_terminals = 0;
  311.         if ((ret = asplit_pattern_flat(APattern, AM, terminals, pnum_terminals, (int *)pAParse)) == -1)
  312.             return -1;
  313.         return ret;
  314.     }
  315. }
  316.  
  317. /*
  318. int
  319. dd(b, e)
  320.     char    *b, *e;
  321. {
  322.     int    i=0;
  323.     extern int anum_terminals;
  324.     extern char amatched_terminals[];
  325.     for(;i<anum_terminals; i++) printf("%d ", amatched_terminals[i]);
  326.     putchar(':');
  327.     while (b != e) putchar(*b++);
  328.     putchar('\n');
  329.     return 1;
  330. }
  331. */
  332.  
  333. /* fast interpreter for the tree using which terminals matched: array bound checks are not done: its recursive */
  334. int
  335. eval_tree(tree, matched_terminals)
  336.     ParseTree    *tree;
  337.     char        matched_terminals[];
  338. {
  339.     int    res;
  340.     if (tree == NULL) {
  341.         fprintf(stderr, "Eval on empty tree: returning true\n");
  342.         return 1;    /* safety sake, but cannot happen! */
  343.     }
  344.     if (tree->type == LEAF) return ((tree->op & NOTPAT) ? (!matched_terminals[tree->terminalindex]) : (matched_terminals[tree->terminalindex]));
  345.     else if (tree->type == INTERNAL) {
  346.         if ((tree->op & OPMASK) == ANDPAT) {    /* sequential evaluation */
  347.             if ((res = eval_tree(tree->data.internal.left, matched_terminals)) != 0) res = eval_tree(tree->data.internal.right, matched_terminals);
  348.             return (tree->op & NOTPAT) ? !res : res;
  349.         }
  350.         else {    /* sequential evaluation */
  351.             if ((res = eval_tree(tree->data.internal.left, matched_terminals)) == 0) res = eval_tree(tree->data.internal.right, matched_terminals);
  352.             return (tree->op & NOTPAT) ? !res : res;
  353.         }
  354.     }
  355.     else {
  356.         fprintf(stderr, "Eval on bad tree: returning false\n");
  357.         return 0;    /* safety sake, but cannot happen! */
  358.     }
  359. }
  360.  
  361. /* [first, last) = C-style range for which we want the words in terminal-values' patterns: 0..num_terminals for !ComplexBoolean, term/term otherwise */
  362. int
  363. asplit_terminal(first, last, pat_buf, pat_ptr)
  364.     int    first, last;
  365.     char    *pat_buf;
  366.     int    *pat_ptr;
  367. {
  368.         int    word_length;
  369.         int    type;
  370.     int    num_pat;
  371.  
  372.     *pat_ptr = 0;
  373.     num_pat = 0;
  374.  
  375.     for (; first<last; first++) {
  376.         word_length = strlen(aterminals[first].data.leaf.value);
  377.         if (word_length <= 0) continue;
  378.         if ((type = checksg(aterminals[first].data.leaf.value, D, 0)) == -1) return -1;
  379.         if (!type) return -1;
  380.         strcpy(&pat_buf[*pat_ptr], aterminals[first].data.leaf.value);
  381.         pat_buf[*pat_ptr + word_length] = '\n';
  382.         pat_buf[*pat_ptr + word_length + 1] = '\0';
  383.         *pat_ptr += (word_length + 1);
  384.         num_pat ++;
  385.         if(num_pat >= MAXNUM_PAT) {
  386.             fprintf(stderr, "Warning: too many words in pattern (> %d): ignoring...\n", MAXNUM_PAT);
  387.             break;
  388.         }
  389.     }
  390.     return num_pat;
  391. }
  392.